package dichotomyMethod;

/*
 *@description 建立四叉树
 *@author hkfan
 *@version 1.0
 *@create 2025/6/30 10:50
 */
public class LeetCode_427 {
    class Node {
        public boolean val;
        public boolean isLeaf;
        public Node topLeft;
        public Node topRight;
        public Node bottomLeft;
        public Node bottomRight;


        public Node() {
            this.val = false;
            this.isLeaf = false;
            this.topLeft = null;
            this.topRight = null;
            this.bottomLeft = null;
            this.bottomRight = null;
        }

        public Node(boolean val, boolean isLeaf) {
            this.val = val;
            this.isLeaf = isLeaf;
            this.topLeft = null;
            this.topRight = null;
            this.bottomLeft = null;
            this.bottomRight = null;
        }

        public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {
            this.val = val;
            this.isLeaf = isLeaf;
            this.topLeft = topLeft;
            this.topRight = topRight;
            this.bottomLeft = bottomLeft;
            this.bottomRight = bottomRight;
        }
    }

    public Node construct(int[][] grid) {
        return solution(grid,0,0,grid.length);
    }

    private Node solution(int[][] grid, int x, int y, int size) {
        if (check(grid,x,y,size)){
            return new Node((grid[x][y]==1)?true:false,true);
        }
        Node res = new Node(true, false);
        res.topLeft=solution(grid,x,y,size/2);
        res.topRight=solution(grid,x,y+size/2,size/2);
        res.bottomLeft=solution(grid,x+size/2,y,size/2);
        res.bottomRight=solution(grid,x+size/2,y+size/2,size/2);
        return res;
    }

    private boolean check(int[][] grid, int x, int y, int size) {
        int res = grid[x][y];
        for (int i = x; i < x + size; i++) {
            for (int j = y; j < y+size; j++) {
                if(grid[i][j]!=res){
                    return false;
                }
            }
        }
        return true;
    }
}
